package by2019;

import java.util.Arrays;

/**
 * 归并排序通常会用到递归，但其实递归并不优。 归并排序需要数列本身是有序的。
 * 
 * 归并操作的工作原理如下：
 * 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 * 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 
 * 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
 * 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾
 * 
 * 如 设有数列{6，202，100，301，38，8，1} 
 * 初始状态：6,202,100,301,38,8,1
 * 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
 * 第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4； 
 * 第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
 * 
 * @author CARRY ME HOME
 * @date 2019年10月30日 上午10:53:20
 */
public class 归并排序 {

	public static void main(String[] args) {

		int[] a = { 1, 3, 5, 7, 9 };
		int[] b = { 2, 4, 6, 8, 10 };
		int[] c = new int[10];

		int aa = 0;
		int bb = 0;
		int cc = 0;

		while (aa < a.length || bb < b.length) {

			if (aa < a.length && a[aa] < b[bb]) {
				c[cc] = a[aa];
				aa++;
			} else {
				c[cc] = b[bb];
				bb++;
			}
			cc++;
		}

		System.out.println(Arrays.toString(c));

	}

}
